//
// Created by 高森森 on 2022/1/31.
//

#ifndef LEETCODE_SOLUTION18_H
#define LEETCODE_SOLUTION18_H

#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>

using namespace std;
class Solution18 {
public:
    vector<vector<int>>cache;
    int  dfs(int l,int r) {
        if(l>=r)
            return 0;
        if(cache[l][r]!=0)
            return cache[l][r];
        int ans=INT_MAX;
        for(int x=l;x<=r;x++) {
            int cur=x+max(dfs(l,x-1),dfs(x+1,r));
            ans=min(ans,cur);
        }
        cache[l][r]=ans;
        return ans;
    }
    int getMoneyAmount(int n) {
        cache=vector<vector<int>>(n+1,vector<int>(n+1));
        return dfs(1,n);
    }
    int getMoneyAmount2(int n) {
        //定义dp函数
        vector<vector<int>>dp(n+2,vector<int>(n+2,0));
        for(int len=2;len<=n;len++)
            for(int i=1;i<=n-len+1;i++)
            {
                int j=i+len-1;
                int m=INT_MAX;
                for(int k=i;k<=j;k++){
                    m=min(m,max(dp[i][k-1],dp[k+1][j])+k);
                }
                dp[i][j]=m;
            }
        return dp[1][n];
    }
};


#endif //LEETCODE_SOLUTION18_H
